package dfs;

public class 省份数量 {
    //dfs    看做一个图，isConnected是图的邻接表
    public int findCircleNum1(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] isVisited = new boolean[n];
        int res=0;
        for (int i = 0; i < n; i++) {
            //没有访问过
            if (!isVisited[i]) {
                dfs(isConnected, isVisited, n, i);
                res++;
            }
        }
        return res;
    }
    private void dfs(int[][] isConnected, boolean[] isVisited, int n, int i) {
        for (int j = 0; j < n; j++) {
            if (isConnected[i][j]==1  && !isVisited[j]){
                isVisited[j] = true;
                dfs(isConnected,isVisited,n,j);
            }
        }
    }
    //并查集解法
    public int findCircleNum(int[][] isConnected) {
         int n = isConnected.length;
        UF uf = new UF(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j]==1)
                    uf.union(i,j);
            }
        }
        return uf.count;
    }
}
class UF {
    // 连通分量个数,独立节点的个数
    public int count;
    // 存储一棵树，存储每个节点的父节点
    public int[] parent;
    // 记录树的“重量”，记录一棵树有多少个节点
    public int[] size;
    public UF(int n) {
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            //初始阶段，每个树的根节点是自己
            parent[i] = i;
            //每个数的节点树为1
            size[i] = 1;
        }
    }
    //连接两颗树
    public void union(int p, int q) {
        //找到p的根节点
        int rootP = find(p);
        int rootQ = find(q);
        //如果根节点相同，说明在同一棵树，直接返回
        if (rootP == rootQ)
            return;
        // 小树接到大树下面，较平衡
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }
    //判断两棵树是否连接
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
    //找到一棵树的根节点
    public int find(int x) {
        while (parent[x] != x) {
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}
